package 我的Java学习_算法基础.day_03;

public class _041_寻找发帖水王 {
    /*
    1.水王ID出现次数大于总次数一半，直接消减
    2.以下代码演示：水王ID出现次数等于总次数一半
     */
    public static void main(String[] args) {
        int[] a ={9,3,9,7,9,7,8,9};
        int key=halfTime(a);
        System.out.println(key);
    }
    private static int halfTime(int[] array){
        //候选数
        int candidate = array[0];
        //出现次数
        int nTimes = 1;
        //最后一个元素出现次数
        int countOfLast = 0;
        int N = array.length;
        //扫描数组
        for (int i = 0; i < N; i++) {
            //统计最后一个元素出现次数
            if(array[i]==array[N-1]) {
                countOfLast++;
            }
            //两两消减为0，应该把现在的元素作为候选数
            if(nTimes==0){
                candidate = array[i];
                nTimes = 1;
                continue;
            }
            //遇到和候选值相同的，次数加一
            if(candidate==array[i]){
                nTimes++;
            }else{
                nTimes--;
            }
        }
        if(countOfLast==N/2){   //最后一个元素是水王ID
            return array[N-1];
        }else{
            return candidate;
        }

    }

}
